package Ep09_DynamicProgram.DP3_0070;

/**
 * @author Jimmy Zhan WORKSTATION
 * @date 2023/7/5 21:10
 * 说明： 0070 爬楼梯
 *      到一阶是一种方法（+1），到二阶两种方法（+1+1，+2）
 *      到三阶就是一阶和二阶的方法数之和，因为我想去三阶，我到了一阶和到了二阶，去三阶的方法都是确定的
 *      因此去三阶的方法数可以分解成 去前一阶的方法数 + 去前两阶的方法数，也就是斐波那契数列
 *      1. 确定dp[i]的含义：dp[i]:第 i次到爬到的楼梯级数的方法数 dp[i]
 *      2. 递推公式：dp[i] = dp[i-1] + dp[i-2]
 *      3. dp[]如何初始化, dp[0] = 0, dp[1] = 1
 *      4. 遍历顺序：从前向后遍历这样才能保证最新的 dp[i-1]和 dp[i-2]
 *      5. 打印 dp[]，用于 debug
 */

public class Mine {
    public int climbStairs(int n) {
        int[] dp = new int[n];
        if (n < 2) return n;
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i < n; i++) {
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n-1] + dp[n-2];
    }
}
